import java.util.*;
import java.io.*;

public class ST {

	public static ArrayList<Node> nodeList; //array der indeholder alle nodes. bruges til debugging. Beh�ver nok ikke at bruge denne, da man bare kan kigge i cList i debuggeren.
	public Node root;
	int size;
	int debug = 0;
	public int lawls;
	public String gutString;
	public ST(String s)
	{
		root = new Node("",null);
		root.marked = true;
		size = 0;
		nodeList = new ArrayList<Node>();
		constructTree(s);
	}
	/*
	 * Denne følger meget konkret http://www.daimi.au.dk/~cstorm/courses/StrAlg_f10/slides/McCreight-2010.pdf 
	 * Algoritmen står meget beskrevet i midten af den pdf.
	 */
	public void constructTree(String input)
	{
		//add the entire string under the root.
		root.addChild(input);
		Node headi = root; //da den f�rste udregning af head(i) der laves, er for i = 1, s� vil denne altid v�re root, da man k�rer for j<i, og man ikke kan have 0.
		String headi2;
		String taili2;
		String v;

		Object[] ssreturn = new Object[2];
		Object[] fsreturn = new Object[2];
		Node insNode = new Node(null,null);
		Node currentNode = root;
		String taili;
		String currentString;
		Node u;
		root.setSuffixLink(root);
		root.setTotalString("");
		Node w = new Node(null,null);
		for(int i = 0; i < input.length()-1; i++) //jeg starter fra 0, da dette g�r at den f�rste iteration kigger p� det eksempel, hvor at vi kigger p� hele strengen.
		{
			debug = i;
			currentString = input.substring(i);
			gutString = currentString;
			String addString = currentString.substring(1); //dette er den string, vi faktisk pr�ver at adde. Kan refaktor den v�k senere, n�r mississippi$ virker.

			if(headi.getStr().length() == 0) //if head(i) = "", then
			{
				taili = currentString;

				ssreturn = slowscan(root,taili.substring(1));//slowscan(root,s(tail(i)))

				headi2 = (String)ssreturn[1];
				currentNode = (Node)ssreturn[0];

				if(headi2 == "") //Hvis head(i+1) er "", skal jeg bare smide tail(i+1) ind efter den node jeg f�r tilbage fra slowscan 
				{
					//add i+1 if necessary
					Node insertNode = new Node(currentString.substring(1),currentNode);
					((Node)ssreturn[0]).addChild(insertNode);
					insertNode.setTotalString(currentString.substring(1));
					insertNode.setInsertNumber(i+2);
					headi = root; // til n�ste iteration, vil headi stadig v�re root.
				}
				else //hvis head(i+1).length() > 0, s� skal jeg adde en node head(i+1) under den node jeg f�r tilbage fra slowscan.
				{
					if(currentNode.getStr().equals(headi2)) //s� skal jeg bare adde tail efter currentString
					{
						String leafi2 = addString.substring(currentNode.getTotalString().length());
						insNode = new Node(leafi2,currentNode);
						currentNode.addChild(insNode);
						insNode.setInsertNumber(i+2);
						insNode.setTotalString(insNode.getParent().getTotalString() + leafi2);
						headi = currentNode; //da jeg ikke inds�tter head(i+1) som node, skal head(i+1) v�re currentNode
						continue;
					}
					else
					{
						//jeg skal inds�tte headi2 mellem currentnode.parent() og currentNode.
						insNode = new Node(headi2,currentNode.getParent());
						insNode.setTotalString(insNode.getParent().getTotalString()+headi2); 
						insNode.addChild(currentNode);
						currentNode.getParent().deleteChild(currentNode);
						currentNode.setParent(insNode);
						currentNode.setStr(currentNode.getStr().substring(insNode.getStr().length()));//jeg sletter fra currentNode, det som der nu st�r i insnode
						insNode.getParent().addChild(insNode);


						//jeg skal ogs� adde taili2 som barn af insnode.
						taili2 = addString.substring(insNode.getTotalString().length());
						Node insNode2 = new Node(taili2,insNode);
						insNode2.setTotalString(insNode2.getParent().getTotalString()+taili2);
						insNode.addChild(insNode2);
						insNode2.setInsertNumber(i+2);

						headi = insNode; //Da jeg inds�tter head(i+1) skal jeg huske at opdatere headi til dette til n�ste iteration.
					}

				}
				continue;
			} //lukker if(headi.getStr().length() == 0)

			u = headi.getParent(); //u = parent(head(i))
			v = headi.getStr();//v = label(u,head(i)). Dette m� v�re strengen i head(i), da dette er det mellem head(i) og dens parent.



			if(u.getStr().length() != 0) //if u != ""
			{
				fsreturn = fastscan(u.getSuffixLink(),v);
			}
			else
			{	
				fsreturn = fastscan(root,v.substring(1)); //v.substring(1) m� v�re v[2..|v|], da vi her starter p� 0 og ikke 1.
			}

			//fsreturn er den jeg bruger til w. Problemet er, at den kan v�re b�d edge og node.
		
			if( ((Node)fsreturn[0]).getStr().length() > ((String)fsreturn[1]).length() ) //if w is an edge
			{
				//add a node for w. Jeg skal alts� bare adde en node fsreturn[1] nede af fsreturn[0]
				currentNode = (Node)fsreturn[0];
				String nodeString = (String)fsreturn[1];

				insNode = new Node(nodeString,currentNode.getParent());
				insNode.setTotalString(insNode.getParent().getTotalString()+nodeString);
				insNode.addChild(currentNode);
				currentNode.getParent().deleteChild(currentNode);
				currentNode.setParent(insNode);
				currentNode.setStr(currentNode.getStr().substring(nodeString.length())); //jeg sletter det fra currentNode, der nu kommer til at st� i den parent.
				insNode.getParent().addChild(insNode);
				//add suffixlink. Jeg har at head(i+1) = w, s� jeg skal bare s�tte mit suffixlink til denne.
				w = insNode;				
			}
			else if( ((Node)fsreturn[0]).getStr().equals((String)fsreturn[1]) ) //if w is a node. Vi ved den er en node her, da vi er Nodens streng NEDE i noden. alts� hele vejen nede.
			{
				ssreturn = slowscan( (Node)fsreturn[0] , currentString.substring( (headi.getTotalString().length()) )); //head(i+1) = slowscan(w,tail(i)). TODO:DENNE ER �NDRET TIL [...] length()+1, da man vil adde currentString.substring(1), og s� finde tail p� denne.					

				//head(i+1) skal addes som node, hvis den ligger p� en edge.

				//da min ssreturn er hvor langt jeg er nede i noden, kan jeg bare sammenligne l�ngden
				currentNode = (Node)ssreturn[0];
				String nodeString = (String)ssreturn[1];

				w = (Node)fsreturn[0]; //denne er ssreturn[0] med mindre jeg kommer ind i denne if-s�tning.
				insNode = currentNode; //dette er bare slowscan(w,tail(i))

				if( currentNode.getStr().length() != nodeString.length() ) //if head(i+1) er en edge, AKA. der skal addes en node.
				{
					insNode = new Node(nodeString,currentNode.getParent());
					insNode.setTotalString(insNode.getParent().getTotalString()+nodeString);
					insNode.addChild(currentNode);
					currentNode.getParent().deleteChild(currentNode);
					currentNode.setParent(insNode);
					currentNode.setStr(currentNode.getStr().substring(nodeString.length())); //jeg sletter det fra currentNode, der nu kommer til at st� i den parent.
					insNode.getParent().addChild(insNode);
				}
			}
			else
			{
				System.out.println("WE ARE FUUUUUUUUUUUUCKED");
			}
			//add leaf i+1 and edge between head(i+1) and i+1. 
			headi.setSuffixLink(w);

			headi = insNode;

			String leafi2 = addString.substring(headi.getTotalString().length());
			Node i2 = new Node(leafi2,headi); //jeg har her opdateret min head(i) til at v�re head(i+1), derfor kan jeg bruge den.
			i2.setTotalString(headi.getTotalString() + leafi2);
			i2.setInsertNumber(i+2);
			headi.addChild(i2);	
		} //denne lukker for-loop 
		return;
	}		

	public void search(String s)
	{
		//find the lowest node, with the entire string.
		Object[] ssreturn = slowscan(root,s);
		Node lowestNode = ((Node)ssreturn[0]);

		if( (lowestNode.getTotalString().startsWith(s)) == false )		
		{
			System.out.println("FUFUFUFUUIF");
			return;
		}
		traverse(lowestNode);
	}


	public void traverse(Node n)
	{
		if(n.amountOfChildren() == 0) //if leaf
		{
			System.out.println(n.getInsertNumber());
			return;
		}
		for(int i = 0;i<n.amountOfChildren();i++)
		{
			traverse(n.cList.get(i));
		}
	}


	public Object[] fastscan(Node from, String to) 
	{

		Object[] returnArray = new Object[2];
		Node currentNode = from;
		String vPart = to;

		if(vPart.equals(""))
		{
			returnArray[0] = currentNode;
			returnArray[1] = "";
			return returnArray;
		}
		int j = 0;

		while(j < currentNode.amountOfChildren())
		{
			if(currentNode.cList.get(j).getStr().charAt(0) == vPart.charAt(0)) //hvis vi kigger ned i det rigtige barn.
			{
				currentNode = currentNode.cList.get(j);					

				if(currentNode.getStr().length() == vPart.length())
				{
					returnArray[0] = currentNode;
					returnArray[1] = vPart; //TODO:jeg har �ndret denne fra "" til vPart.
					return returnArray;
				}
				else if(currentNode.getStr().length() > vPart.length()) //jeg har fundet min node. vPart er over 0, s� denne kan jeg tjekke p� senere.
				{
					returnArray[0] = currentNode;
					returnArray[1] = vPart;
					return returnArray;
				}
				else
				{
					vPart = vPart.substring(currentNode.getStr().length());
					j = 0;
					continue;
				}
			}
			else
			{
				j++;
			}
		}
		System.out.println("fastscan shouldnt get down here. this just returns null :(. This means, that the string to wasent found below node from. This shouldnt be possible.");
		return null;
	}

	public Object[] slowscan(Node from, String to) //find det st�rste prefix af to, som allerede kan findes fra den node man st�r i. s(tail(i)) er at slette det f�rste tegn fra tail(i) aka. to.
	{
		Object[] returnArray = new Object[2]; //plads 1 er den node vi stod i(og derfor skal inds�tte under), og plads 2 giver mig HVOR LANGT jeg er nede i denne node. hvis plads 2.length() == node.length(), s� st�r jeg bare iden node.
		Node currNode = from;
		String cut = to; //dette er det, som er tilbage af strengen.
		String howFar = to; //added
		int howFarDown = 0;
		returnArray[0] = currNode;
		returnArray[1] = currNode.getStr(); //jeg initializerer denne til dette, da hvis den ikke kommer igennem to ikke ligger i barnet af from, skal man bare retunere from. Dog er man helt nede i from, og derfor skal strengen v�re from.getStr().

		int i = 0;
		int h = 0;
		while( i < currNode.amountOfChildren() ) //for(int i = 0; i < currNode.cList.size();i++) //<= da den ogs� skal k�re den sidste gang, s� jeg f�r mulighed for at resette i.
		{
			/*
			 * NOTE: hvis jeg f�r en node tilbage, og min streng er af samme l�ngde som denne node, vil jeg st� i noden.!
			 */

			if(cut.length() == 0)
			{
				System.out.println("fail");
				returnArray[0] = currNode;
				returnArray[1] = "";
				return returnArray;
			}
			if( currNode.cList.get(i).getStr().charAt(0) == cut.charAt(0) )
			{
				howFarDown = 0;
				currNode = currNode.cList.get(i);
				h = 0;

				while(currNode.getStr().charAt(h) == cut.charAt(0) )
				{
					howFarDown++;
					if(cut.length() == 0) //de kan v�re ens, fordi de begger er den tomme streng. Dette if bliver kun brugt i f�rste iteration, og i dette tilf�lde, er vi "" nede i strengen.
					{
						System.out.println("here?");
						returnArray[0] = currNode;
						returnArray[1] = "";
						return returnArray;
					}

					cut = cut.substring(1);

					if(cut.length() == 0) //jeg tjekker ogs� efter at jeg har cuttet af min string.
					{
						returnArray[0] = currNode;
						returnArray[1] = currNode.getStr().substring(0, howFar.length()-cut.length());
						return returnArray;
					}
					if(currNode.getStr().length() == h+1) //hvis vi har n�et sidste element i currNode. -1 da strings starter p� pos 0.
					{
						if(cut.length() > 0) //hvis den stre;ng vi s�ger efter, er st�rre end den der findes i vores node.
						{ //n�r jeg skifter node, skal jeg ogs� opdatere min howFar.
							howFar = howFar.substring(currNode.getStr().length());

							i = 0;
							break;
						}
					}
					h++;
				}


			}
			else
			{
				i++;
				continue; //g�r at man ikke k�rer nedenst�ende. Bliver brugt, hvis man starter i en node, og ingen af dens b�rn matcher to. S� skal jeg s�rge for, at jeg ikke �ndrer i min initializering.
			}

			returnArray[0] = currNode;
			returnArray[1] = currNode.getStr().substring(0, howFarDown);
			if(howFarDown < currNode.getStr().length()) //TODO: har added den her part, da den ellers gik ind i et barn, selvom den stod p� en edge i parent af dette barn.
			{
				return returnArray;
			}
		} //lukker ydereste while

		//dette er den special-case, hvor man vil inds�tte $ under en node. jeg skal her retunere returnArray[0] som noden, og returnArray[1] som strengen for noden, da jeg st�r helt nede.
		if(currNode.getTotalString().equals(to.substring(0, to.length()-1)))
		{
			returnArray[1] = currNode.getStr();
		}

		return returnArray;
	}

	public String LCP(String s, int i, int j) 
	{
		String xone = s.substring(i-1); //substring(i) cutter de første i bogstaver af strengen, men LCP starter med det bogstav der står på i. Derfor skal jeg bruge i-1
		String xtwo = s.substring(j-1);
		String returnString = "";

		for(int h=0; h < xone.length(); h++) //den skal bare køre op til en af stengenes længde. Den kommer højest sandsynligt til at break inden da.
		{
			if( xone.charAt(h) == xtwo.charAt(h) )
			{
				returnString = returnString + xone.charAt(h); //da de er ens, skal jeg bare tage char fra en af dem.
			}
			else
			{
				break; //hvis de ikke er ens, breaker jeg.
			}
		}
		return returnString;
	}

	public String head(String s, int i)
	{

		if(i > s.length()) //burde smide en exception
		{
			System.out.println("i too large...");
			return "";
		}
		//head er den længste LCP. Så jeg kan bare regne LCP i et loop, og så kun overskrive, hvis den nye værdi er større. Man skal regne LCP(i,j) for alle j < i
		int j = 1;
		String currentHead = "";
		String calcHead = "";
		while(j<i)
		{
			calcHead = LCP(s,j,i);
			if(calcHead.length() > currentHead.length())
			{
				currentHead = calcHead;
			}
			j++;
		}

		return currentHead;
	}

}